// https://www.lintcode.com/problem/partition-array-by-odd-and-even/

class Solution {
public:
    /*
     * @param nums: an array of integers
     * @return: nothing
     */
     
    void partion(vector<int> &nums, int start, int end) 
    {
        int low = start;
        int high = end;
        int mid = (high - low) / 2 + low;
        while (low < high)
        {
            while (nums[low] % 2 == 1) low++;
            while (nums[high] % 2 == 0) high--;
            if (low <= high)
            {
                swap(nums[low++], nums[high--]);
            }
        }
        // partion(nums, start, high);
        // partion(nums, low, end); 不是排序，不需要两边都交换过。只需要过一遍就可以了
    }
    void partitionArray(vector<int> &nums) {
        partion(nums, 0, nums.size() - 1);
    }
};